<?php

function leq2($a1,$a2,$b1,$b2){
  return ($a1<$b1 or $a1==$b1 and $a2<=$b2);
}

function leq3($a1,$a2,$a3,$b1,$b2,$b3){
  return ($a1<$b1 or $a1==$b1 and ($a2<$b2 or $a2==$b2 and $a3<=$b3));
}

function radixpass(&$a,&$b,&$r,$n,&$k){
  $f=chr(ord(reset($k))-1);
  $c=array($f=>0);
  foreach($k as $letter){$c[$letter]=0;}
  for($i=0;$i<$n;++$i){
    ++$c[$r[$a[$i]]];
  }

  $sum=0;
  foreach($c as $letter=>$i){
    $c[$letter]=$sum;
    $sum+=$i;
  }
  for($i=0;$i<$n;++$i) $b[$c[$r[$a[$i]]]++]=$a[$i];
  unset($c);
}


function sortSuffixArray(&$s,&$SA,$n,&$alpha){
  $n0=floor(($n+2)/3);
  $n1=floor(($n+1)/3);
  $n2=floor($n/3);
  $n02=$n0+$n2;

  $SA12=array_fill(0,$n02+3,0);
  $SA0=array_fill(0,$n0,0);  

  $s12=array();
  $max=$n+($n0-$n1);
  for($i=0;$i<$max;++$i) if($i%3 != 0) $s12[] = $i;
  $s12[]=$s12[]=$s12[]=0;

  radixpass($s12,$SA12,array_slice($s,2),$n02,$alpha);
  radixpass($SA12,$s12,array_slice($s,1),$n02,$alpha);
  radixpass($s12,$SA12,$s,$n02,$alpha);

  $name=0;
  $array_name=array(0);
  $c0=$c1=$c2=-1;
  for($i=0;$i<$n02;++$i){
    if($s[$SA12[$i]]!=$c0 or $s[$SA12[$i]+1]!=$c1 or $s[$SA12[$i]+2]!=$c2){
      $array_name[]=++$name;
      $c0=$s[$SA12[$i]];
      $c1=$s[$SA12[$i]+1];
      $c2=$s[$SA12[$i]+2];      
    }
    if($SA12[$i]%3==1){$s12[floor($SA12[$i]/3)]=$name;}
    else              {$s12[floor($SA12[$i]/3) + $n0]=$name;}
  } 
  if($name < $n02){
    sortSuffixArray($s12,$SA12,$n02,$array_name);
    for($i=0;$i<$n02;++$i) $s12[$SA12[$i]]=$i+1;
  }
  else{
    for($i=0;$i<$n02;++$i) $SA12[$s12[$i]-1]=$i;
  }

  unset($array_name);

  for($i=0;$i<$n02;++$i){
    if($SA12[$i]<$n0) $s0[]=3*$SA12[$i];
  }

  radixpass($s0,$SA0,$s,$n0,$alpha);

  for($p=0, $t=$n0-$n1, $k=0; $k<$n; ++$k){
    $i = ($SA12[$t] < $n0) ? $SA12[$t]*3 + 1 : ($SA12[$t] - $n0)*3+2;
    $j = $SA0[$p];
    if(
      ($SA12[$t] < $n0) ?
      leq2($s[$i],$s12[$SA12[$t]+$n0],$s[$j],$s12[floor($j/3)]) :
      leq3($s[$i],$s[$i+1],$s12[$SA12[$t]-$n0+1],$s[$j],$s[$j+1],$s12[floor($j/3)+$n0])      
    ){
      $SA[$k]=$i;
      if(++$t==$n02) for($k++;$p<$n0;++$p,++$k) $SA[$k]=$SA0[$p];
    }
    else{
      $SA[$k]=$j;
      if(++$p==$n0){
        for($k++;$t<$n02;++$t,++$k){
          $SA[$k]=($SA12[$t] < $n0) ? $SA12[$t]*3 + 1 : ($SA12[$t] - $n0)*3+2;
        } 
      }
    }
  }
  unset($s12);
  unset($SA12);
  unset($SA0);
  unset($s0);
}


?>
